\documentclass{article}

\usepackage{gastex}
\usepackage[usenames]{color}
\usepackage[T1]{fontenc}

\renewcommand{\labelenumi}{\alph{enumi})}
\renewcommand{\labelenumii}{\arabic{enumii})}


\begin{document}

\textbf{Aufgabe:}\\
Schreiben Sie reguläre Ausdrücke für die folgenden Sprachen:

\begin{enumerate}
	\item 
	Die Menge aller Zeichenreihen aus Nullen und Einsen, derart, dass alle Paar aufeinander folgender Nullen vor allen Paaren aufeinander folgenden Einsen stehen.
	
	\item
	Die Menge aller Zeichenreihen aus Nullen und Einsen, deren Anzahl von Nullen durch 5 teilbar ist.
		
\end{enumerate}

\textbf{Lösung:}
\begin{enumerate}
	\item
	$(10+0)^{\ast}(\varepsilon+1)(01+1)^{\ast}(\varepsilon+0)$\\
	Erklärung: Der Ausdruck ist aufgeteilt in zwei Teile: vorne und hinten. Lauf Aufgabenstellung darf vorne alles auftreten, was die form $00...0$ hat oder die Form $1010....10$, bzw. Kombinationen dieser Zeichenketten; deshalb $(10 + 0)^{\ast}$. Jetzt besteht noch die Möglichkeit, dass am Ende dieser Zeichenreihe eine $1$ steht, oder nicht (in diesem Fall stünde am Ende eine $0$, dies ist aber durch $(10 + 0)^{\ast}$ abgedeckt) deswegen hängen wir ein $(\varepsilon + 1)$ an. Damit wäre der vordere Teil der Zeichenreichen beschrieben: alles was aus beliebig vielen Nullen und keinen aufeinander folgenden Einsen besteht:$(10+0)^{\ast}(\varepsilon+1)$\\
	Jetzt kommen wir zum hinteren Teil des Ausdrucks, und hier verhält es sich ähnlich, wie im vorderen Teil, nur eben analog genau anders herum. Jetzt dürfen alle Zeichenreichen kommen, die aus belibig vielen Einsen und keinen aufeinander folgenden Nullen bestehen. Analog gebildet zu obeb sieht das wie folgt aus: $(01 + 1)^{\ast}(\varepsilon + 0)$\\
	Nun hängt man beides aneinander wie in der Aufgabenstellung verlangt. Erst alles mit Paaren von Nullen und keinen Paaren von Einsen, und hinten dran alles aus Paaren von Einsen und keinen Paaren von Nullen: $(10+0)^{\ast}(\varepsilon+1)(01+1)^{\ast}(\varepsilon+0)$
	
	\item
	$((\varepsilon + 1)0(\varepsilon + 1)0(\varepsilon + 1)0(\varepsilon + 1)0(\varepsilon + 1)0(\varepsilon + 1))^{\ast}$\\
	Erklärung: Die Konstruktion dieses Ausdrucks geht rein logisch von statten. Erstes Kriterium: Anzahl der Nullen muss 0, 5, 10, .... sein (durch 5 teilbar). Dies erreicht man am einfachsten in dem man fünf aufeinander folgende Nullen als Ausdruck formuliert: $(00000)^{\ast}$. Damit wäre das Problem mit den 5 Nullen gelöst. Wo packt man die Einsen hin?\\
	Die Einsen können im Grunde ÜBERALL auftreten; vor, zwischen und nach den Nullen. Deshalb fügen wir ein $(\varepsilon + 1)$ vor und nach jede Null, denn es KANN eine Eins vor und nach jeder Null kommen, MUSS aber nicht:\\
	$((\varepsilon + 1)0(\varepsilon + 1)0(\varepsilon + 1)0(\varepsilon + 1)0(\varepsilon + 1)0(\varepsilon + 1))^{\ast}$\\
	Da zwischen den Nullen aber auch mehr als eine Eins auftreten kann, wird vom Ausdruck $(\varepsilon + 1)$ die Kleensche Hülle gebildet:\\
	$((\varepsilon + 1)^{\ast}0(\varepsilon + 1)^{\ast}0(\varepsilon + 1)^{\ast}0(\varepsilon + 1)^{\ast}0(\varepsilon + 1)^{\ast}0(\varepsilon + 1)^{\ast})^{\ast}$\\
	Jetzt sind alle Zeichenreichen abgedeckt, die, wenn fünf Nullen auftreten, vor und nach jeder Null beliebig viele Einsen stehen haben kann. Jedoch beschreibt dieser Ausdruck NICHT den Fall, dass KEINE Null auftritt, jedoch aber eine Folge von Einsen. Deshalb wird vorn oder hinten ein $(\varepsilon + 1)^{\ast}$ angehängt. Jetzt können auch beliebig viele Einsen auftreten, ohne dass eine Null kommt. Kommt irgendwann eine Zeichenkette, die Nullen enthält, dann ist sichergestellt, dass sie eine durch 5 teilbare Anzahl Nullen enthält.\\
	$((\varepsilon + 1)^{\ast}0(\varepsilon + 1)^{\ast}0(\varepsilon + 1)^{\ast}0(\varepsilon + 1)^{\ast}0(\varepsilon + 1)^{\ast}0(\varepsilon + 1)^{\ast})^{\ast}(\varepsilon + 1)^{\ast}$



\end{enumerate}

	

\end{document}